//
// Description: 33. 搜索旋转排序数组
// Created by Loading on 2021/4/7.
//

#include <bits/stdc++.h>

using namespace std;

//有序数组旋转后的二分查找，二分后必然有一侧有序
int search(vector<int> &nums, int target) {
    int n = nums.size();
    if (n == 1) {
        return nums[0] == target ? 0 : -1;
    }

    int l = 0, r = n - 1;
    while (l <= r) {
        /* 虽然题目给出了数据范围保证了 l + r 不可能越界，但仍要注意，最好使用 l + (r - l) / 2 的方式 */
        //int mid = (l + r) / 2;
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[0] <= nums[mid]) {//左侧为有序
            if (nums[0] <= target && nums[mid] > target) {//目标数在左侧
                r = mid - 1;
            } else {//目标数在右侧
                l = mid + 1;
            }
        } else {//左侧若为无序，则右侧必有序
            if (nums[mid] < target && nums[n - 1] >= target) {//目标数在右侧
                l = mid + 1;
            } else {//目标数在左侧
                r = mid - 1;
            }
        }
    }

    return -1;
}

int main() {
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    cout << search(nums, 3) << endl;
}